Lexical Analysis

Token class

A token class corresponds to a set of strings, following a certain rule.

Same substring could have different meanings in different contexts. To disambiguate, one functionality that a lexical analysis must have is lookahead to decide whether one token ends and the next token begins. For example, to distinguish = assignment from == equality judgement.

To conclude, the goal of lexical analysis is to

1. Partition the input string into lexemes
2. Identify the token of each lexeme

If we do a left-to-right scan for lexical analysis, then lookahead is required.

Regular languages (regular expressions) are used to identify token classes. Regex can be constructed by atomic regex (single character and epsilon) and compound operators (union, concat, iteration).

• epsilon: a set of empty string, i.e., \(\set{\texttt{""}}\)
• union: \(A+B=\set{s : s\in A \lor s\in B}\)
• concat: \(AB=\set{ab: a\in A \land b\in B}\)
• iteration: \(A^\ast=\cup_{i\ge 0} A^i\), where \(A^i\) means concat \(A\) to itself by \(i\) times.